package org.usmile.algorithms.leetcode.middle;

/**
 * 43. 字符串相乘
 *
 * 给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
 * 注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
 *
 * 示例 1:
 * 输入: num1 = "2", num2 = "3"
 * 输出: "6"
 *
 *  示例 2:
 * 输入: num1 = "123", num2 = "456"
 * 输出: "56088"
 *
 *  提示：
 * 1 <= num1.length, num2.length <= 200
 * num1 和 num2 只能由数字组成。
 * num1 和 num2 都不包含任何前导零，除了数字0本身。
 */
public class _0043 {
    public static void main(String[] args) {
        new _0043_Solution().multiply("0", "123");
    }
}

class _0043_Solution {
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }

        int[] res = new int[num1.length() + num2.length()];
        for (int i = num1.length() - 1; i >= 0; i--) {
            int x = num1.charAt(i) - '0';
            for (int j = num2.length() - 1; j >= 0; j--) {
                int y = num2.charAt(j) - '0';
                int sum = res[i + j + 1] + x * y;
                res[i + j + 1] = sum % 10;
                res[i + j] += sum / 10;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < res.length; i++) {
            if (i == 0 && res[i] == 0) {
                continue;
            }
            sb.append(res[i]);
        }

        return sb.toString();
    }
}

class _0043_Solution1 {
    public String multiply(String num1, String num2) {
        if (num1.length() < num2.length()) {
            String temp = num1;
            num1 = num2;
            num2 = temp;
        }

        String result = "0";
        int i = num2.length() - 1;
        while (i >= 0) {
            int currNum = num2.charAt(i) - '0';
            if (currNum != 0) {
                StringBuilder curr = new StringBuilder();
                int j = num1.length() - 1;
                int carry = 0;
                while (j >= 0) {
                    int x = num1.charAt(j) - '0';
                    int product = x * currNum + carry;
                    curr.append(product % 10);
                    carry = product / 10;

                    j--;
                }

                if (carry != 0) {
                    curr.append(carry);
                }
                curr.reverse();
                curr.append("0".repeat(Math.max(0, num2.length() - 1 - i)));
                result = addStrings(result, curr.toString());
            }

            i--;
        }

        return result;
    }

    private String addStrings(String num1, String num2) {
        StringBuilder sb = new StringBuilder();
        int carry = 0;
        int i = num1.length() - 1;
        int j = num2.length() - 1;
        while (i >= 0 || j >= 0) {
            int x = i < 0 ? 0 : num1.charAt(i) - '0';
            int y = j < 0 ? 0 : num2.charAt(j) - '0';
            int sum = x + y + carry;
            sb.append(sum % 10);
            carry = sum / 10;
            i--;
            j--;
        }
        if (carry != 0) {
            sb.append(carry);
        }

        return sb.reverse().toString();
    }
}
